/**
 * @author gao
 * @date 2025/7/12 10:34
 */

public class RBTree {

    /**
     * @return 判断是否符合红黑树的性质
     */
    public boolean isRBTree() {
        if (root == null) {
            return true;
        }
        if (root.color != COLOR.BLACK) {
            System.out.println("违反性质：根节点必须为黑色");
        }
        int blackNum = 0;
        RBTreeNode cur = root;
        while (cur != null) {
            if (cur.color == COLOR.BLACK) {
                blackNum++;
            }
            cur = cur.left;
        }
        return checkRedColor(root) && checkBlackNum(root, 0, blackNum);
    }

    /**
     * @param root 传入根节点
     * @return 是否有两个连续的红色节点
     */
    public boolean checkRedColor(RBTreeNode root) {
        if (root == null) {
            return true;
        }
        // 如果根节点的颜色为红色，则检查其父节点的颜色
        if (root.color == COLOR.RED) {
            RBTreeNode parent = root.parent;
            // 如果父节点的颜色也为红色，则违反了红黑树的性质，返回false
            if (parent.color == COLOR.RED) {
                System.out.println("违反性质：两个红色节点连在一起");
                return false;
            }
        }
        // 递归检查左子树和右子树
        return checkRedColor(root.left) && checkRedColor(root.right);
    }

    /**
     * @param root         根节点
     * @param pathBlackNum 每次递归的时候，计算每个黑色节点的数量
     * @param blackNum     事先计算好每条路径上黑色节点的数量
     * @return 判断每条路径上的黑色节点数量是否相同
     */
    public boolean checkBlackNum(RBTreeNode root, int pathBlackNum, int blackNum) {
        if (root == null) {
            return true;
        }

        // 如果当前节点为黑色节点，则路径黑色节点数量加1
        if (root.color == COLOR.BLACK) {
            pathBlackNum++;
        }

        // 如果当前节点为叶子节点，则判断路径黑色节点数量是否等于给定的黑色节点数量
        if (root.left == null && root.right == null) {
            if (pathBlackNum != blackNum) {
                System.out.println("违反了性质：每条路径上的黑色节点数量不一样");
                return false;
            }
        }
        // 递归判断左子树和右子树
        return checkBlackNum(root.left, pathBlackNum, blackNum)
                && checkBlackNum(root.right, pathBlackNum, blackNum);
    }

    /**
     * @param root 中序遍历
     */
    public void InOrder(RBTreeNode root) {
        if (root == null) {
            return;
        }
        InOrder(root.left);
        System.out.print(root.val + " ");
        InOrder(root.right);
    }

    // 节点定义
    static class RBTreeNode {
        public RBTreeNode left;
        public RBTreeNode right;
        public RBTreeNode parent;
        public int val;
        public COLOR color;

        public RBTreeNode(int val) {
            this.val = val;
            this.color = COLOR.RED;
        }
    }

    public RBTreeNode root;

    /**
     * @param val 插入
     * @return 是否插入成功
     */
    public boolean insert(int val) {
        RBTreeNode node = new RBTreeNode(val);
        if (root == null) {
            root = node;
            root.color = COLOR.BLACK;
            return true;
        }
        RBTreeNode parent = null;
        RBTreeNode cur = root;

        while (cur != null) {
            if (cur.val < val) {
                parent = cur;
                cur = cur.right;
            } else if (cur.val == val) {
                return false;
            } else {
                parent = cur;
                cur = cur.left;
            }
        }

        // 此时cur引用为空
        if (parent.val < val) {
            parent.right = node;
        } else {
            parent.left = node;
        }

        node.parent = parent;
        cur = node;

        // 调整颜色
        while (parent != null && parent.color == COLOR.RED) {
            RBTreeNode grandFather = parent.parent;
            if (parent == grandFather.left) {
                RBTreeNode uncle = grandFather.right;
                if (uncle != null && uncle.color == COLOR.RED) {
                    parent.color = COLOR.BLACK;
                    uncle.color = COLOR.BLACK;
                    grandFather.color = COLOR.RED;
                    cur = grandFather;
                    parent = cur.parent;
                } else {
                    if (cur == parent.left) {
                        RotateLeft(parent);
                        RBTreeNode tmp = parent;
                        parent = cur;
                        cur = tmp;
                    }
                    // uncle节点为空 或者 uncle节点为黑色
                    RotateRight(grandFather);
                    grandFather.color = COLOR.RED;
                    parent.color = COLOR.BLACK;
                }
            } else {
                // p为g的右孩子节点
                RBTreeNode uncle = grandFather.left;
                if (uncle != null && uncle.color == COLOR.RED) {
                    parent.color = COLOR.BLACK;
                    uncle.color = COLOR.BLACK;
                    grandFather.color = COLOR.RED;
                    cur = grandFather;
                    parent = cur.parent;
                } else {
                    if (cur == parent.left) {
                        RotateRight(parent);
                        RBTreeNode tmp = parent;
                        parent = cur;
                        cur = tmp;
                    }
                    // uncle节点为空 或者 uncle节点为黑色
                    RotateLeft(grandFather);
                    grandFather.color = COLOR.RED;
                    parent.color = COLOR.BLACK;
                }
            }
        }
        root.color = COLOR.BLACK;
        return true;
    }

    /**
     * @param parent 左单旋
     */
    private void RotateLeft(RBTreeNode parent) {
        RBTreeNode subR = parent.right;
        RBTreeNode subRL = subR.left;

        parent.right = subRL;
        subR.left = parent;
        if (subRL != null) {
            subRL.parent = parent;
        }

        RBTreeNode parent1 = parent.parent;
        parent.parent = subR;

        if (root == parent) {
            root = subR;
            root.parent = null;
        } else {
            if (parent1.left == parent) {
                parent1.left = subR;
            } else if (parent1.right == parent) {
                parent1.right = subR;
            }
            subR.parent = parent1;
        }
    }

    /**
     * @param parent 右单旋
     */
    private void RotateRight(RBTreeNode parent) {
        RBTreeNode subL = parent.left;
        RBTreeNode subLR = subL.right;

        parent.left = subLR;
        subL.right = parent;
        if (subLR != null) {
            subLR.parent = parent;
        }
        RBTreeNode parent1 = parent.parent;
        parent.parent = subL;

        if (parent == root) {
            root = subL;
            root.parent = null;
        } else {
            if (parent1.left == parent) {
                parent1.left = subL;
            } else if (parent1.right == parent) {
                parent1.right = subL;
            }
            subL.parent = parent1;
        }
    }
}